In the field of consumer or compact electronics (CE), devices typically employ numerous software programs, firmware drivers, communications protocols and security protocols on top of an operating system (OS) (e.g., proprietary OS, PALM OS, Windows CE, embedded Linux, etc.).
At least some of the programs, drivers, and protocol data may relate to sensitive material such as private and public cryptographic keys and security algorithms for decrypting and encrypting transmissions to and from the CE device. Accordingly, it is desirable for manufacturers of CE devices to secure sensitive software, firmware, and security information that reside on a long term memory (e.g., a flash memory) of the CE device. By doing so, manufacturers may prevent malicious users from circumventing device security features such as the Contents Scrambling System (CSS) algorithm used to enable copy protection in Digital Versatile Discs (DVDs), for example.
Currently, the security of long term memory in CE devices is lacking. Some devices attempt to use the operating system to secure the file system, but most operating systems do not provide adequate security for their file systems. Other methods may implement security with password protection or through the basic input/output system (BIOS), but these methods are limited, under user control and/or only provide weak security.
Further, manufacturers may wish to perform secure large-scale upgrades to CE device software for a plurality of CE devices. This may be done through the use of conventional symmetric cryptographic algorithms, which allow pairs of users, who each share a common secret key, to exchange private messages even when communicating over a public network (e.g., the Internet). Such systems possess very fast software implementations, inexpensive and fast hardware implementations, and, most importantly, are very secure. In fact, their security simply relies on one-way functions: functions f that are relatively easy to evaluate but hard to invert, that is, for which it is hard, given a generic value z=f(x), to find any value y such that f1(y)=z. Block ciphers such as the Data Encryption Standard (DES) and triple DES (3DES), for example, are based on Fiestal networks and are invertible. One-way hash functions are one-way (and thus not invertible), as they are a many to one mapping. The security of symmetric cryptographic methods results from their output being nearly indistinguishable (to an extent) from a randomly generated output.
Despite these main advantages, conventional symmetric cryptosystems are not very useful for large-scale communications platforms in which several users require secured communication with each other. Prior exchange of a common secret key (e.g., by physically meeting in a secure location) with every person with whom one wants to communicate in private may be difficult.
To overcome this difficulty, several asymmetric cryptographic methods have been developed that allow two people to agree on common secret keys in a convenient manner. Asymmetric cryptographic methods are far more expensive computationally than symmetric cryptographic methods. Unfortunately, until now all publicly known protocols for this task are based either on the assumed computational difficulty of a particular number theory problem (as in the Diffie-Hellman and the Rivest Shamir Adleman (RSA) algorithms), or they rely on an unrealistic amount of trust.
In the case of RSA, the encryption function f(x) typically is xe mod n, where n is a publicly-known product of two large prime integers P1 and P2 (known only to the user who publishes n and e), and e (a publicly known exponent relatively prime with P1 and P2). In the RSA system, if a user X publishes two values e and n as above, then user Y can select a secret key k in an arbitrary manner and communicate it privately to X, by looking up X's publicized values, computing k′=ke mod n, and sending k′ to X over a public network. If it is virtually impossible to calculate the eth-root-modulo of a composite integer, the factorization of which is not known, then only user X will be able to retrieve k from k′; indeed, only X knows n's factorization (i.e., P1 and P2), and this knowledge makes extracting the eth root feasible, though not trivial.
In the case of the Diffie-Hellman scheme, the protocol has two system parameters p and g. They are both public and may be used by all the users in a system. Parameter p is a prime number and parameter g (usually called a generator) is an integer less than p, where for every number n between 1 and p-1 inclusive, there is a power k of g such that n=gk mod p.
Suppose Alice and Bob want to agree on a shared secret key using the Diffie-Hellman key agreement protocol. They proceed as follows: First, Alice generates a random private value a, and Bob generates a random private value b. Both a and b are drawn from the set of integers. Then they derive their public values using parameters p and g and their private values. Alice's public value is ga mod p and Bob's public value is gb mod p. They then exchange their public values. Finally, Alice computes gab=(gb)a mod p, and Bob computes gba=(ga)b mod p. Since gab=gba=k, Alice and Bob now have a shared secret key k.
The protocol depends on the Discrete Logarithm Problem for its security. It assumes that it is computationally infeasible to calculate the shared secret key k=gab mod p given the two public values ga mod p and gb mod p when the prime p is sufficiently large. It has been shown that breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms under certain assumptions.
The Diffie-Hellman key exchange, however, is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants.
For both the RSA and the Diffie-Hellman algorithms, the operations involved for secret-key exchange are quite time-consuming in software (computations of the type ab mod c are not-trivial whenever these values are large), or they require complex and expensive VLSI chips for fast modular exponentiation. Thus, building large-scale systems having efficient secret-key exchange using such techniques may require a great financial investment.
More importantly, the assumptions of the above secret-key exchange schemes to ensure security are very rigid. In the case of RSA, secret-key exchange is performed by means of an encryption function, f(x)=xe mod n, which possesses a secret (i.e., the factorization of n) that, if known, makes the inversion of f (i.e., computing x from f(x)) possible rather than practically impossible. While it is widely believed that one-way functions exist, fewer researchers believe that one-way functions possess this additional property. Similarly, in the case of Diffie-Hellman, gx mod p not only needs to be one-way, but it should also possess additional algebraic and multiplicative properties. It is doubtful that one-way functions satisfying such additional algebraic constraints exist. Indeed, continuous algorithmic advances are being made that make factoring integers and solving the Discrete Logarithm Problem easier.
The methods described above do not provide a computationally efficient means to achieve secret-key exchange. Other algebraic secret-key exchange schemes have been devised by Blom and by Blundo et al., but these schemes rely upon an unrealistic amount of trust. In fact, not only do these schemes require a central authority that knows all the individual secret keys of the users, but also that all of the users in a large system are trustworthy. For instance, in Blom's case, as described in an article titled “An Optimal Class of Symmetric Key Generation Systems,” Advances in Cryptology: Proceedings of Eurocrypt 84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1985, pp. 335-338, a trusted authority prepares and distributes keys to a group of n users. All these keys will remain secret, unless k of the users collaborate and reveal to each other the keys in their possession. If this happens, they can compute the secret keys of every other user in the system.
With such schemes, moreover, a few bad users may achieve the same results as a large number of bad users by forcing good users to surrender their secret keys. In other schemes forcing some users to reveal their keys may allow an enemy to understand at most the communications of those users (who will be aware of having lost privacy). In these algebraic schemes, however, an enemy who has forced a sufficient number of users to reveal their secret keys will understand the communications of all users, which is obviously unacceptable.
In another embodiment of the prior art, the RSA public key system may be used for secret-key exchange. Briefly, the RSA public key system defines a private key spr and a public key spu, Private key spr is used to sign messages, where the public key spu may be used to verify the signature. Messages may then be transmitted securely with encryption using the public key, E(message, spu), where E(x,y) is an encryption operation that encrypts a value x with a key y. The message may then be decrypted using the private key by computing D(E(message, spu),spr), where D(x,y) is a decryption operation that decrypts a value x with a key y. Therefore, only the holder of the private key can decrypt documents encrypted with its corresponding public key. Accordingly, a user can create a private-public key pair (spr, spu) and make spu public so that anyone can send encrypted documents securely to the user or verify the user's signature. Keeping spu in a publicly available location presents a problem, however, in that a malicious user may replace spu with its own public key apu, and perform a man-in-the-middle attack to intercept encrypted documents. Furthermore, RSA implementations are computationally expensive and may require a large hardware footprint (e.g., about 150 k gates for 512 bit RSA keys).
In summary, therefore, the prior art techniques described above are often inadequate for secret-key exchange systems to be used on resource-starved devices, such as CE devices, for example. As a result, it may not be feasible to secure communication links between service providers and compact electronic devices for the purpose of upgrading or, generally, communicating with the devices. The RSA and Diffie-Hellman cryptographic systems described above, for example, require expensive computing power in order to be implemented and may not be viable options for implementation in consumer or compact electronics.
Other systems have been developed that utilize a trusted authority to disseminate secret keys to members of a group that wish to communicate securely between each other. Such systems, however, may not be scalable. Additionally, an untrustworthy member may compromise such systems, if the member makes public the secret keys given to it by the trusted authority.
CE devices typically include a central processing unit (CPU), a memory and a memory management unit (MMU) that controls access to the memory. The device may also include long-term storage such as a disk drive or flash memory. A file system, managed by the OS, is created for data stored in the long-term storage. The MMU may also implement address mapping so that programs or data from the long-term storage may be transferred into the memory for execution or use. In a memory-mapped input/output (I/O) environment, the CPU accesses the data by sending commands to the long-term storage device as a peripheral device using an address and a command. The MMU then passes the command to the appropriate peripheral (i.e. the long-term storage device) based on the address which controls the transfer of data between the peripheral and the memory. Critical information for the CE device, such as the OS and encryption keys, are typically stored on the long-term storage device. In presently available systems, however, because transfers between the long-term storage device are not checked, it may be possible to corrupt this critical information.